// https://www.lintcode.com/problem/maximum-average-subarray/

public class Solution {
    /**
     * @param nums: an array
     * @param k: an integer
     * @return: the maximum average value
     */
    public double findMaxAverage(int[] nums, int k) {
        // Write your code here
        int ret = 0, avg = 0;
        for (int i = 0; i < k; ++i) {
            ret += nums[i];
        }
        avg = ret;
        for (int i = k; i < nums.length; ++i) {
            avg += nums[i] - nums[i - k];
            if (avg > ret) {
                ret = avg;
            }
        }
        return (double)ret / (double)k;
    }
}